package Solutions;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/***
 * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，
 * 判断 nums 中是否存在四个元素 a，b，c 和 d ，
 * 使得 a + b + c + d 的值与 target 相等？
 * 找出所有满足条件且不重复的四元组。
 *
 * 注意：
 *
 * 答案中不可以包含重复的四元组。
 *
 * 示例：
 *
 * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 *
 * 满足要求的四元组集合为：
 * [
 *   [-1,  0, 0, 1],
 *   [-2, -1, 1, 2],
 *   [-2,  0, 0, 2]
 * ]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/4sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FourSum {

    /**
     * 从一个整型数组中选出 4 个元素，使得它们的和为给定的 target 值
     * 每个解不重复
     * @param nums 给定的整型数组
     * @param target 给定的目标值
     * @return 解集合
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();// 用于记录解
        if (nums == null || nums.length < 4) {// 当nums为空或者长度不足4的时候，直接返回空解即可
            return result;
        }
        if (nums.length == 4) {// 长度==4，计算所有元素的值，和给定的 target 值进行比较
            int res = 0;
            for (int num : nums) {// 求和
                res += num;
            }
            if (res == target) {// 与给定的 target 的值一致：构造结果返回即可
                result.add(Arrays.asList(nums[0], nums[1], nums[2], nums[3]));
            }
            return result;
        }
        Arrays.sort(nums);// 排序，便于后续地筛选
        System.out.println(Arrays.toString(nums));
        int a, b, c, d, left, right, tmp, tar, index;// 进行筛选需要的一些临时变量
        for (int i = 0; i < nums.length - 3; i++) {// 遍历数组，除去最后3项
            a = nums[i];// 参考值a,构成解的第一个元素，用target-a作为三数之和的目标 "target"
            for (index = i + 1; index < nums.length - 2; index++) {// 以下为与三数之和类似的处理方式
                if (nums[index] == nums[index - 1] && index != i + 1) {
                    continue;// 去重
                }
                b = nums[index];// 构成解的第二个元素，需要去重
                left = index + 1;// 左指针
                right = nums.length - 1;// 右指针
                while (left < right) {// 当左右指针没有重合的时候，说明在剩余的元素中，还有其他的元素
                    c = nums[left];
                    d = nums[right];
                    tar = target - a;
                    tmp = b + c + d;// 用于转换为三数和的 target
                    if (tmp == tar) {// 如果相等的话，那么将4个元素包装成 List 放入到结果集中
                        result.add(Arrays.asList(a, b, c, d));
                        left++;
                        right--;// 移动指针
                        while (left < right && nums[left] == nums[left - 1]) left++;// 去重
                        while (right > left && nums[right + 1] == nums[right]) right--;
                    } else if (tmp < tar) {// 如果比较小的话，移动左指针，使得和变大
                        left++;
                        while (left < right && nums[left] == nums[left - 1]) left++;// 去重
                    } else {// 如果比较大的话，移动右指针，使得和缩小
                        right--;
                        while (right > left && nums[right + 1] == nums[right]) right--;// 去重
                    }
                }
            }
            while (nums[i + 1] == a && i < nums.length - 3) {// 对于使用过的a值，不再使用，去重
                i++;
            }
        }
        return result;// 返回结果集
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-7, -5, 0, 7, 1, 1, -10, -2, 7, 7, -2, -6, 0, -10, -5, 7, -8, 5};
        System.out.println(new FourSum().fourSum(nums, 28));
        System.out.println("高效方法");
        System.out.println(new FourSum()._fourSum(nums, 28));
    }


    public List<List<Integer>> _fourSum(int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n - 3; i++) {
            //跳过重复元素
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                //跳过重复元素
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                //双指针
                int k = j + 1, l = n - 1;
                //获取当前范围内最值
                int min = nums[i] + nums[j] + nums[k] + nums[k + 1];
                int max = nums[i] + nums[j] + nums[l] + nums[l - 1];
                if (min > target || max < target) {
                    continue;
                }
                while (k < l) {
                    int sum = nums[i] + nums[j] + nums[k] + nums[l];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
                        //跳过重复元素
                        while (k < l && nums[k] == nums[k + 1]) {
                            k++;
                        }
                        while (k < l && nums[l] == nums[l - 1]) {
                            l--;
                        }
                        k++;
                        l--;
                    } else if (sum < target) {
                        k++;
                    } else {
                        l--;
                    }

                }
            }
        }
        return res;
    }


}
